import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution2242 {
    public int maximumScore(int[] scores, int[][] edges) {
        int ans=-1;
        int[] first=new int[scores.length];
        Arrays.fill(first,-1);
        int[] next=new int[edges.length*2];
        int[] go=new int[edges.length*2];
        int cur=0;
        for (int[] edge : edges) {
            next[cur]=first[edge[0]];
            first[edge[0]]=cur;
            go[cur]=edge[1];
            cur++;
            next[cur]=first[edge[1]];
            first[edge[1]]=cur;
            go[cur]=edge[0];
            cur++;
        }
        int[] one=new int[scores.length];
        int[] two=new int[scores.length];
        int[] three=new int[scores.length];
        Arrays.fill(one,-1);
        Arrays.fill(two,-1);
        Arrays.fill(three,-1);
        for (int i=0;i<scores.length;i++){
            int p=first[i];
            while (p!=-1){
                int v=go[p];
                if (one[i]==-1 || scores[v]>scores[one[i]]){
                    three[i]=two[i];
                    two[i]=one[i];
                    one[i]=v;
                }else if (two[i]==-1 || scores[v]>scores[two[i]]){
                    three[i]=two[i];
                    two[i]=v;
                }else if (three[i]==-1 || scores[v]>scores[three[i]]){
                    three[i]=v;
                }
                p=next[p];
            }
        }
        for (int[] edge : edges) {
            if (two[edge[0]]==-1 || two[edge[1]]==-1){
                continue;
            }
            int t=scores[edge[0]]+scores[edge[1]];
            int ta=one[edge[0]]==edge[1]?two[edge[0]]:one[edge[0]];
            int tb=one[edge[1]]==edge[0]?two[edge[1]]:one[edge[1]];
            if (ta!=tb){
                ans=Math.max(ans,t+scores[ta]+scores[tb]);
            } else{
                Set<Integer> set=new HashSet<>();
                set.add(edge[0]);
                set.add(edge[1]);
                set.add(ta);
                int target=-1;
                int[] ints=new int[]{two[edge[0]],two[edge[1]],three[edge[0]],three[edge[1]]};
                for (int anInt : ints) {
                    if (anInt!=-1 && !set.contains(anInt) && scores[anInt]>target){
                        target=scores[anInt];
                    }
                }
                if (target!=-1){
                    ans=Math.max(ans,t+scores[ta]+target);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution2242().maximumScore(new int[]{5,2,9,8,4},new int[][]{{0,1},{1,2},{2,3},{0,2},{1,3},{2,4}}));
    }
}
